1) Field of the Invention
The present invention relates to a technology for converting virtual addresses to actual addresses.
2) Description of the Related Art
These days virtual storage systems have been widely used. The virtual storage systems have a bigger storage space (a virtual storage space), which can be used virtually, than the storage space of a computer system (an actual storage space). Both the actual storage space and the virtual storage space are divided into blocks called pages.
A correlation between the virtual address of a virtual page in the virtual storage space and the actual address of an actual page in the actual storage space is stored in a list table called a page table. The page table is referred to when converting the virtual address to the actual address.
Though the page table is usually stored in a random access memory (RAM), the process of referring to the page table every time the virtual address is to be converted to the actual address slows down the translation process.
As a countermeasure, an address translation cache, called a translation look-aside buffer (TLB), which can be accessed much faster than the RAM, is installed in a CPU. The correlation between the recently converted virtual addresses and the actual addresses are maintained in the TLB. The TLB serves as an easy reference for subsequent conversions of virtual address to the actual address, thereby enhancing the translation speed of the addresses.
The TLB may be composed of two types of memories: RAM and a content addressable memory (CAM). The TLB that is composed of a RAM (hereinafter, “TLB-RAM”) implements a set-associative method of an associativity of one or greater to store more TLB entries.
The TLB that is composed of the CAM (hereinafter, “TLB-CAM”) circumvents the limitations on the page size that can be stored in the TLB-RAM and can efficiently search pages of various sizes.
The TLB entries stored in the TLB are assigned a page size. The page size is of four types: 8 kilo-byte page, 64 kilo-byte page, 512 kilo-byte page, and 4 mega-byte page.
Since the TLB-RAM can register only one type of page size by virtue of its structure, two RAMs are provided which can register TLB entries of 8 kilo-byte page and 4 M byte page. On the other hand, the TLB-CAM can register the TLB entries of all types of page sizes and can register a special TLB entry referred to as a locked entry.
The TLB replaces the TLB entries when information pertaining to a requested virtual address is not found in the TLB entries and there is no space to add new TLB entries. Locked entries are those entries that cannot be replaced with other TLB entries by the TLB.
Conventional technologies can be found in Japanese Patent Laid-Open Publication Nos. 3-20847, 5-81132, and 10-49545.
However, in the conventional technology, when two or more programs use the same virtual address, the TLB entries used by these programs get concentrated in one area of the TLB-RAM (for instance, area corresponding to the first 40 mega-bytes), thereby causing thrashing in which a plurality of programs scramble the area where the TLB entries are registered.
In other words, the TLB-RAM uses a part of the virtual address as an index address, which carries out the indexing of the TLB entries stored in the TLB-RAM. Consequently, when two or more programs simultaneously use the same virtual address, the hit rate of TLB is adversely drops.
Increasing the associativity of the TLB mitigates the occurrence of the thrashing phenomenon. However, increasing the associativity of the TLB makes the circuit complicated and difficult to implement.